package indi.caspar.algorithms;


import java.util.Arrays;

/**
 * Created by casparhuan on 2017/3/1.
 */
public class SortUtil<T> {

    public static void main(String[] args) {
        SortUtil<Integer> sortUtil = new SortUtil<Integer>();
        Integer[] t = {1,5,1,2,4,3,6,8,9,45,21,3,8,0,54,6,5,0,0,0,2,4,6,2};
        sortUtil.print(t);
        sortUtil.print(sortUtil.simpleInsertionSort(t,1));
    }


    public T[] simpleInsertionSort(final T[] disorderArray ,int unSortedIndex){
        if ( unSortedIndex < disorderArray.length){
            int min = -1;
            for (int j = unSortedIndex-1 ; j >=0 ; j--) {
                if (((Comparable)disorderArray[unSortedIndex]).compareTo(((Comparable)disorderArray[j]))< 0 ){
                    min =  j;
                }else{
                    break;
                }
            }
            if (min != -1) {
                insertToArray(disorderArray, unSortedIndex, min);
                print(disorderArray);
            }
            simpleInsertionSort(disorderArray,++unSortedIndex);
        }
        return disorderArray;
    }

    /**
     * 简单插入排序
     * @param disorderArray
     * @return
     */
    public T[] simpleInsertionSort(final T[] disorderArray){
        for (int i = 1; i < disorderArray.length ; i++) {
            int min = -1;
            for (int j = i-1 ; j >=0 ; j--) {
                if (((Comparable)disorderArray[i]).compareTo(((Comparable)disorderArray[j]))< 0 ){
                    min =  j;
                }else{
                    break;
                }
            }
            if (min != -1) {
                insertToArray(disorderArray, i, min);
                print(disorderArray);
            }
        }
        return disorderArray;
    }

    private void insertToArray(T[] disorderArray, int srcIndex, int toIndex) {
        T temp = disorderArray[srcIndex];
        if (srcIndex > toIndex) {
            for (int i = srcIndex; i > toIndex; i--) {
                disorderArray[i] = disorderArray[i - 1 ];
            }
            disorderArray[toIndex] = temp;
        }else{
            disorderArray[srcIndex]  = disorderArray[toIndex];
            disorderArray[toIndex] = temp;
        }
    }

    public void print(final T[] data){
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }


}
